import java.util.Arrays;

/**
 * Created by zhourh on 2018/6/15.
 * 给定两个字符串 s 和 t，它们只包含小写字母。

 字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

 请找出在 t 中被添加的字母。



 示例:

 输入：
 s = "abcd"
 t = "abcde"

 输出：
 e

 解释：
 'e' 是那个被添加的字母。

 位运算
 */
public class FindTheDifference {

    public static void main(String[] args) {
        System.out.println(new FindTheDifference().findTheDifference2("abcd", "abcde"));
        System.out.println(new FindTheDifference().findTheDifference2("recwert", "wertccer"));
    }

    /**
     * 排序后遍历，找到不同
     * 时间复杂度为 O((2nlogn) + n)
     * @param s
     * @param t
     * @return
     */
    public char findTheDifference(String s, String t) {
        if (s == null || t == null) {
            return 0;
        }

        if (t.length() != s.length() + 1) {
            return 0;
        }

        char[] sArray = s.toCharArray();
        char[] tArray = t.toCharArray();

        Arrays.sort(sArray);
        Arrays.sort(tArray);

        for (int i = 0; i < tArray.length; i++) {
            if (i >= sArray.length) {
                return tArray[i];
            }

            if (tArray[i] != sArray[i]) {
                return tArray[i];
            }
        }

        return 0;
    }

    /**
     * 直接利用^位运算，相当于从一个数组中找到唯一一个不同值
     * 时间复杂度为O(2n)
     * @param s
     * @param t
     * @return
     */
    public char findTheDifference2(String s, String t) {
        if (s == null || t == null) {
            return 0;
        }

        if (t.length() != s.length() + 1) {
            return 0;
        }

        char result = 0;

        for (int i = 0; i < s.length(); i++) {
            result ^= s.charAt(i);
        }

        for (int i = 0; i < t.length(); i++) {
            result ^= t.charAt(i);
        }

        return result;
    }
}
